CLEMENT Romain - RUBINI Thomas - VACHET Audric
Groupe A2-6

Rapport de modélisations mathématiques - projet Infographie

1. Introduction

L'objectif de ce notebook est de présenter l'utilisation des coordonnées homogènes pour la création et l'optimisation d'une animation en deux dimensions en Python à l'aide du module d'animation de la bibliothèque Matplotlib.

2. Animations

Dans le monde de l'animation (2D comme 3D), l'objectif principal pour mettre en mouvement un objet (une forme géométrique, par exemple un carré) est de modifier les coordonnées de chaque point qui le compose.

Afin de ne pas obtenir un mouvement saccadé, on applique plusieurs fois à la suite une même transformation mineure à une fréquence élevée, ce qui permet d'avoir un mouvement lisse.

Les transformations

Nous avons distingué trois transformations de base :

• La translation
• La rotation autour de l'origine
• L'homothétie à l'origine

Pour chacune de ces transformation, il existe une matrice qui permet la modification d'un point $P$ de coordonnées $\binom{x}{y}$ en un point $P'$ de coordonnées $\binom{x'}{y'}$.

Par exemple pour la translation, on définit le vecteur $ T = \binom{T_{x}}{T_{y}} $. On a :

$$ P + T = P' $$$$ \Leftrightarrow \begin{pmatrix} x \\ y \end{pmatrix} + \begin{pmatrix} T_{x} \\ T_{y} \end{pmatrix} = \begin{pmatrix} x + T_{x} \\ y + T_{y} \end{pmatrix} = \begin{pmatrix} x' \\ y' \end{pmatrix} $$

3. Les coordonnées homogènes

Les coordonnées homogènes sont un système de coordonnées qui servent à exprimer un point dans $ \mathbb{R}^{n} $ à l'aide d'un vecteur de $ n+1 $ valeurs. Autrement dit, un point en deux dimensions gagne une nouvelle coordonnée, que l'on fixe à 1 :

$$ \begin{pmatrix} x \\y \end{pmatrix} \rightarrow \begin{pmatrix} x \\ y \\ 1 \end{pmatrix} $$

Grace aux coordonnées homogènes, il est possible d'exprimer les transformations listées précédemment à l'aide d'une matrice de taille $ 3 \times 3 $ :

Translation

Nous pouvons donc définir $ T $ notre nouvelle matrice de translation :

$$ T = \begin{pmatrix} 1 & 0 & T_{x} \\ 0 & 1 & T_{y} \\ 0 & 0 & 1 \end{pmatrix} $$

Nous avons désormais :

$$ T \cdot P = P' $$$$ \Leftrightarrow \begin{pmatrix} 1 & 0 & T_{x} \\ 0 & 1 & T_{y} \\ 0 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} x \\ y \\ 1 \end{pmatrix} = \begin{pmatrix} x + T_{x} \\ y + T_{y} \\ 1 \end{pmatrix} = \begin{pmatrix} x' \\ y' \\ 1 \end{pmatrix} $$

Exemple par le code

# Imports
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
from matplotlib import rc
from matplotlib.animation import FuncAnimation
from math import cos, sin, pi

# Configuration de matplotlib
matplotlib.rcParams['animation.embed_limit'] = 2**128
plt.rcParams["animation.html"] = "jshtml"
plt.rcParams['figure.dpi'] = 150

###############
# TRANSLATION #
###############

def appliquer_translation(Tx, Ty, m=np.identity(3)):
    # Nous créons la matrice de coordonées homogènes
    matriceTranslation = np.array([
        [1, 0, Tx],
        [0, 1, Ty],
        [0, 0,  1]
    ])
    # "@" permet de multiplier les matrices (tableau numpy)
    return m @ matriceTranslation

# Le point que nous voulons translater
# Il a pour coordonnées (0, 0) plus sa coordonnée homogène Z
point = np.array([0, 0, 1])

# Les paramètres de la translation
Tx = 2      # Composante X du vecteur de translation
Ty = -1     # Composante Y du vecteur de translation

# Création de la matrice de translation
T = appliquer_translation(Tx, Ty)

print("Position initiale :", point[:2])
# Nous génèrons 5 images
for i in range(5):
    # P' = T * P
    point = T @ point
    print("Position à l'image %i :" % (i + 1), point[:2])

Position initiale : [0 0]
Position à l'image 1 : [ 2. -1.]
Position à l'image 2 : [ 4. -2.]
Position à l'image 3 : [ 6. -3.]
Position à l'image 4 : [ 8. -4.]
Position à l'image 5 : [10. -5.]

Visualisation avec Matplotlib

fig, ax1 = plt.subplots()

ax1.set_aspect('equal', adjustable='box')
# Définition de la taille initiale du plan
ax1.set_xlim(-10, 10)
ax1.set_ylim(-10, 10)

point = np.array([0, 0, 1])
Tx = 0.2
Ty = -0.1
T = appliquer_translation(Tx, Ty)
circle = plt.Circle(point[:2], 0.2)

def init():
    return circle,

def update(_):
    global point
    point = T @ point
    circle.set_center(point[:2])
    ax1.add_artist(circle)
    return circle,

anim = FuncAnimation(fig=fig, func=update, frames=50, interval=50, blit=True, cache_frame_data=False, init_func=init)
plt.close(fig)
anim

Once Loop Reflect

Rotation à l'origine

Pour trouver la matrice homogène qui permet une rotation d'angle $ \theta $ autour de l'origine du repère, nous partons du système à deux équations (sans les coordonnées homogènes, donc)

$$ \left\{ \begin{array}{lr} x' = x \cos{\theta} - y \sin{\theta} \\ y' = x \sin{\theta} + y \cos{\theta} \end{array} \right. $$

Nous ajoutons notre coordonnée homogène $z$ au système

$$ \Leftrightarrow \left\{ \begin{array}{lr} x' = x \cos{\theta} - y \sin{\theta} \\ y' = x \sin{\theta} + y \cos{\theta} \\ z' = z \end{array} \right. $$

Notre objectif est de trouver une matrice de rotation $R_{0}$ telle que :

$$ R_{0} \cdot P = P' $$$$ \Leftrightarrow R_{0} \cdot \begin{pmatrix} x \\ y \\ 1 \end{pmatrix} = \begin{pmatrix} x' \\ y' \\ 1 \end{pmatrix} $$

Nous choisissons donc :

$$ R_{0} = \begin{pmatrix} \cos{\theta} & -\sin{\theta} & 0 \\ \sin{\theta} & \cos{\theta} & 0 \\ 0 & 0 & 1 \end{pmatrix}$$

Nous avons bien :

$$ \begin{pmatrix} \cos{\theta} & -\sin{\theta} & 0 \\ \sin{\theta} & \cos{\theta} & 0 \\ 0 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} x \\ y \\ 1 \end{pmatrix} = \begin{pmatrix} x \cos{\theta} - y \sin{\theta} \\ x \sin{\theta} + y \cos{\theta} \\ 1 \end{pmatrix} = \begin{pmatrix} x' \\ y' \\ 1 \end{pmatrix} $$

Exemple par le code

########################
# ROTATION À l'ORIGINE #
########################

def appliquer_rotation_origine(theta, m=np.identity(3)):
    # Nous créons la matrice de coordonées homogènes
    matriceRotation = np.array([
        [cos(theta), -sin(theta), 0],
        [sin(theta),  cos(theta), 0],
        [         0,           0, 1]
    ])
    return m @ matriceRotation

# Le point que nous voulons tourner
# Il a pour coordonnées (1, 0) plus sa coordonnée homogène Z
point = np.array([1, 0, 1])

# Paramètre de la rotation
theta = pi / 4     # Angle de la rotation

# Création de la matrice de rotation
R0 = appliquer_rotation_origine(theta)

print("Position initiale :", point[:2])
# Nous génèrons 5 images
for i in range(5):
    # P' = R0 * P
    point = R0 @ point
    point = np.array(list(map(lambda v: round(v, 15), point)))
    print("Position à l'image %i :" % (i + 1), point[:2])

Position initiale : [1 0]
Position à l'image 1 : [0.70710678 0.70710678]
Position à l'image 2 : [0. 1.]
Position à l'image 3 : [-0.70710678  0.70710678]
Position à l'image 4 : [-1.  0.]
Position à l'image 5 : [-0.70710678 -0.70710678]

Visualisation avec Matplotlib

fig, ax1 = plt.subplots()

ax1.set_aspect('equal', adjustable='box')
# Zoom bounding box
ax1.set_xlim(-10, 10)
ax1.set_ylim(-10, 10)

point = np.array([1, 0, 1])
theta = pi/40
R0 = appliquer_rotation_origine(theta)
circle = plt.Circle(point[:2], 0.2)

def init():
    return circle,

def update(_):
    global point
    point = R0 @ point
    circle.set_center(point[:2])
    ax1.add_artist(circle)
    return circle,

anim = FuncAnimation(fig, update, frames=50, interval=50, blit=True, cache_frame_data=False, init_func=init)
plt.close(fig)
anim

Once Loop Reflect

Homothétie à l'origine

De la même manière que pour la rotation autour de l'origine, pour trouver la matrice homogène qui permet de réaliser une homothétie à l'origine du repère de facteur $s$, nous partons du système à deux équations (sans les coordonnées homogènes, donc)

$$ \left\{ \begin{array}{lr} x' = sx \\ y' = sy \end{array} \right. $$

Nous ajoutons notre coordonnée homogène $z$ au système

$$ \Leftrightarrow \left\{ \begin{array}{lr} x' = sx \\ y' = sy \\ z' = z \end{array} \right. $$

Notre objectif est de trouver une matrice d'homothétie $H_{0}$ telle que :

$$ H_{0} \cdot P = P' $$$$ \Leftrightarrow H_{0} \cdot \begin{pmatrix} x \\ y \\ 1 \end{pmatrix} = \begin{pmatrix} x' \\ y' \\ 1 \end{pmatrix} $$

Nous choisissons donc :

$$ H_{0} = \begin{pmatrix} s & 0 & 0 \\ 0 & s & 0 \\ 0 & 0 & 1 \end{pmatrix}$$

Nous avons bien :

$$ \begin{pmatrix} s & 0 & 0 \\ 0 & s & 0 \\ 0 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} x \\ y \\ 1 \end{pmatrix} = \begin{pmatrix} sx \\ sy \\ 1 \end{pmatrix} = \begin{pmatrix} x' \\ y' \\ 1 \end{pmatrix} $$

Exemple par le code

##########################
# HOMOTHÉTIE À L'ORIGINE #
##########################

def appliquer_homothetie_origine(s, m=np.identity(3)):
    # Nous créons la matrice de coordonées homogènes
    matriceHomothetie = np.array([
        [s, 0, 0],
        [0, s, 0],
        [0, 0, 1]
    ])
    return m @ matriceHomothetie

# Le point que nous voulons transformer
# Il a pour coordonnées (2, -1) plus sa coordonnée homogène Z
point = np.array([2, -1, 1])

# Paramètre de l'homothétie
s = 2

# Création de la matrice de rotation
H0 = appliquer_homothetie_origine(s)

print("Position initiale :", point[:2])
# Nous génèrons 5 images
for i in range(5):
    # P' = H0 * P
    point = H0 @ point
    point = np.array(list(map(lambda v: round(v, 15), point)))
    print("Position à l'image %i :" % (i + 1), point[:2])

Position initiale : [ 2 -1]
Position à l'image 1 : [ 4. -2.]
Position à l'image 2 : [ 8. -4.]
Position à l'image 3 : [16. -8.]
Position à l'image 4 : [ 32. -16.]
Position à l'image 5 : [ 64. -32.]

Visualisation avec Matplotlib

from matplotlib.patches import Polygon

fig, ax1 = plt.subplots()

ax1.set_aspect('equal', adjustable='box')
# Zoom bounding box
ax1.set_xlim(-10, 10)
ax1.set_ylim(-10, 10)

points = np.array([
    [1, 2, 2, 1],
    [2, 2, 1, 1],
    [1, 1, 1, 1]
])
s = 1.1
H0 = appliquer_homothetie_origine(s)

polygon = Polygon([(0, 0)])
ax1.add_artist(polygon)

def update(_):
    global points
    points = H0 @ points
    polygon.set_xy(list(zip(points[0], points[1])))
    return polygon,

anim = FuncAnimation(fig, update, frames=50, interval=50, blit=True, cache_frame_data=False)
plt.close(fig)
anim

Once Loop Reflect

4. Utilité de l'écriture sous forme de multiplication

Une propriété qui découle de l'utilisation de produits de matrices est la possibilité de combiner les transformations. Il est désormais possible de multiplier plusieurs matrices de transformation (translation, rotation, homothétie) car elles ont toutes la même taille de $ 3 \times 3 $, le résultat de cette multiplication est une nouvelle matrice de taille $ 3 \times 3 $ qui permet d'appliquer toute la suite de mouvements à notre point $P$.

Rotation

Bien que nous sachions déjà faire tourner un point autour de l'origine, il est possible de choisir un autre centre de rotation (que nous notons $C = \binom{x_{C}}{y_{C}}$) en combinant deux translations et une rotation à l'origine. Pour cela, nous suivons les étapes suivantes :

1. Translater le point $P$ d'un vecteur $\binom{-x_{C}}{-y_{C}}$
2. Effectuer une rotation à l'origine d'angle $\theta$
3. Translater le résultat d'un vecteur $\binom{x_{C}}{y_{C}}$

Suivre ces étapes va donner l'illusion que le point $P$ a effectué une rotation autour du point $C$. La matrice globale de ce mouvement (notée $R$) peut être obtenue en multipliant les matrices des trois transformations effectuées. Nous avons donc :

$$ R = T_{2} \cdot R_{0} \cdot T_{1} $$

Avec $T_{1}$ la matrice de translation de l'étape 1, $R_{0}$ la rotation à l'origine de l'étape 2 et $T_{2}$ la translation de l'étape 3.

Exemple par le code

############
# ROTATION #
############

def appliquer_rotation(xC, yC, theta, m=np.identity(3)):
    matrice_rotation = appliquer_translation(xC, yC, m)
    matrice_rotation = appliquer_rotation_origine(theta, matrice_rotation)
    matrice_rotation = appliquer_translation(-xC, -yC, matrice_rotation)
    return matrice_rotation

# Le point que nous voulons tourner
# Il a pour coordonnées (0, 0) plus sa coordonnée homogène Z
point = np.array([0, 0, 1])

# Paramètres de la rotation
xC, yC = (1, 0)     # Coordonnées du point C, centre de rotation
theta = -pi / 2     # Angle en radians (sens direct)

# Création de la matrice de rotation
R = appliquer_rotation(xC, yC, theta)

print("Position initiale :", point[:2])
# Nous génèrons 4 images
for i in range(4):
    # P' = R * P
    point = R @ point
    # Nous arrondissons les valeurs pour éviter les erreurs d'imprécisions des nombres décimaux
    point = np.array(list(map(lambda v: round(v, 15), point)))
    print("Position à l'image %i :" % (i + 1), point[:2])

Position initiale : [0 0]
Position à l'image 1 : [1. 1.]
Position à l'image 2 : [2. 0.]
Position à l'image 3 : [ 1. -1.]
Position à l'image 4 : [0. 0.]

Visualisation avec Matplotlib

fig, ax1 = plt.subplots()

ax1.set_aspect('equal', adjustable='box')
# Zoom bounding box
ax1.set_xlim(-10, 10)
ax1.set_ylim(-10, 10)

point = np.array([0, 0, 1])
xC, yC = (3, 1)
theta = -pi/20
R = appliquer_rotation(xC, yC, theta)
circle = plt.Circle(point[:2], 0.2)

def init():
    return circle,

def update(_):
    global point
    point = R @ point
    circle.set_center(point[:2])
    ax1.add_artist(circle)
    return circle,

anim = FuncAnimation(fig, update, frames=40, interval=50, blit=True, cache_frame_data=False, init_func=init)
plt.close(fig)
anim

Once Loop Reflect

Homothétie

De la même manière que pour la rotation, il est possible de choisir un autre "centre d'homothétie" (que nous notons $C = \binom{x_{C}}{y_{C}}$) en combinant deux translations et une homothétie à l'origine. Pour cela, nous suivons les étapes suivantes :

1. Translater le point $P$ d'un vecteur $\binom{-x_{C}}{-y_{C}}$
2. Effectuer une homothétie à l'origine d'échelle $s$
3. Translater le résultat d'un vecteur $\binom{x_{C}}{y_{C}}$

Suivre ces étapes va donner l'illusion que le point $P$ a effectué une homothétie ayant pour centre le point $C$. La matrice globale de ce mouvement (notée $H$) peut être obtenue en multipliant les matrices des trois transformations effectuées. Nous avons donc :

$$ H = T_{2} \cdot H_{0} \cdot T_{1} $$

Avec $T_{1}$ la matrice de translation de l'étape 1, $H_{0}$ l'homothétie à l'origine de l'étape 2 et $T_{2}$ la translation de l'étape 3.

Exemple par le code

##############
# HOMOTHÉTIE #
##############

def appliquer_homothetie(xC, yC, s, m=np.identity(3)):
    matrice_homothetie = appliquer_translation(xC, yC, m)
    matrice_homothetie = appliquer_homothetie_origine(s, matrice_homothetie)
    matrice_homothetie = appliquer_translation(-xC, -yC, matrice_homothetie)
    return matrice_homothetie

# Le point qu'on veut transformer
# Il a pour coordonnées (1,1) plus sa coordonnée homogène Z
point = np.array([1, 1, 1])

# Paramètres de la rotation
xC, yC = (-1, 0)     # Coordonnées du point C, "centre d'homothetie"
s = 2                # Échelle de l'homothetie

# Création de la matrice de rotation
H = appliquer_homothetie(xC, yC, s)

print("Position initiale :", point[:2])
# Nous génèrons 4 images
for i in range(4):
    # P' = H * P
    point = H @ point
    # Nous arrondissons les valeurs pour éviter les erreurs d'imprécisions des nombres décimaux
    point = np.array(list(map(lambda v: round(v, 15), point)))
    print("Position à l'image %i :" % (i + 1), point[:2])

Position initiale : [1 1]
Position à l'image 1 : [3. 2.]
Position à l'image 2 : [7. 4.]
Position à l'image 3 : [15.  8.]
Position à l'image 4 : [31. 16.]

Visualiation avec Matplotlib

fig, ax1 = plt.subplots()

ax1.set_aspect('equal', adjustable='box')
# Zoom bounding box
ax1.set_xlim(-10, 10)
ax1.set_ylim(-10, 10)

points = np.array([
    [1, 3, 3, 1],
    [3, 3, 1, 1],
    [1, 1, 1, 1]
])
xC, yC = (2, 2)
s = 1.05
H = appliquer_homothetie(xC, yC, s)

def update(_):
    global points
    points = H @ points
    l = []
    l.append(*ax1.fill(points[0], points[1]))
    return l

anim = FuncAnimation(fig, update, frames=40, interval=50, blit=True, cache_frame_data=False)
plt.close(fig)
anim

Once Loop Reflect

5. Conclusion

Nous avons désormais toutes les cartes en main pour créer une animation composée de formes géométriques réalisant des mouvements simples mais puissants (notamment si nous les combinons).

Nous avons aussi eu l'occasion de noter un point sur l'optimisation du nombre de calculs effectués. En effet, l'utilisation des coordonnées homogènes permet de réduire le nombre de multiplications de matrices, ce qui fait gagner du temps à l'exécution.

Exemple : Imaginons que nous souhaitons appliquer une rotation de centre $C$ au point $P$ pendant $n$ images (nous répétons $n$ fois la rotation)

• Sans l'utilisation des coordonnées homogènes

  • Pour chaque image, nous appliquons les 3 mouvements qui permettent la rotation autour de $C$
  • Nous avons donc 2 additions et 1 multiplication par image $ \Rightarrow 3n $ opérations

• Avec l'utilisation des coordonnées homogènes

  • Nous pré-calculons notre matrice de transformation ($T_{2} \cdot R_{0} \cdot T_{1}$) $ \Rightarrow 2 $ multiplications
  • Pour chaque image nous multiplions la matrice de transformation par les coordonnées du point ($1$ opération par image)
  • Au total, nous avons donc $n+2$ opérations

L'utilisation des coordonnées homogènes est donc plus efficace car moins d'opérations sont effectuées.

6. Implication des membres de l'équipe

• Romain CLEMENT : $1 \over 3$
  • Création de l'animation
• Thomas RUBINI : $1 \over 3$
  • Développement de l'environnement pour la création de l'animation
• Audric VACHET : $1 \over 3$
  • Rédacteur principal du Jupyter Notebook et du diaporama de présentation